翻訳と辞書 Words near each other ・ Distichochlamys ・ Distichodontidae ・ Distichodus ・ Distance geometry problem ・ Distance Learning and Telemedicine Grant and Loan Program ・ Distance line ・ Distance matrices in phylogeny ・ Distance matrix ・ Distance measures (cosmology) ・ Distance measuring equipment ・ Distance medley relay ・ Distance model ・ Distance modulus ・ Distance of closest approach of ellipses and ellipsoids ・ Distance Only Makes the Heart Grow Fonder ・ Distance oracle ・ Distance sampling ・ Distance stars ・ Distance State University ・ Distance transform ・ Distance Vector Multicast Routing Protocol ・ Distance-bounding protocol ・ Distance-hereditary graph ・ Distance-regular graph ・ Distance-transitive graph ・ Distance-vector routing protocol ・ Distanced from Reality ・ Distances Between Ports ・ Distances shorter than 1 pm ・ Distancia Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Distance oracle ： ウィキペディア英語版 Distance oracle In computing, a distance oracle (DO) is a data structure for calculating distances between vertices in a graph. == Introduction == Let ''G''(''V'',''E'') be an undirected, weighted graph, with ''n'' = |''V''| nodes and ''m'' = |''E''| edges. We would like to answer queries of the form "what is the distance between the nodes ''s'' and ''t''?". One way to do this is just run the Dijkstra algorithm. This takes time $O(m\; +\; n\; \backslash log\; n)$, and requires no extra space (besides the graph itself). In order to answer many queries more efficiently, we can spend some time in pre-processing the graph and creating an auxiliary data structure. A simple data structure that achieves this goal is a ''matrix'' which specifies, for each pair of nodes, the distance between them. This structure allows us to answer queries in constant time $O(1)$, but requires $O(n^2)$ extra space. It can be initialized in time $O(n^3)$ using an all-pairs shortest paths algorithm, such as the Floyd–Warshall algorithm. A DO lies between these two extremes. It uses less than $O(n^2)$ space in order to answer queries in less than $O(m\; +\; n\; \backslash log\; n)$ time. Most DOs have to compromise on accuracy, i.e. they don't return the accurate distance but rather a constant-factor approximation of it. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Distance oracle」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.